package leetcode_top;
import java.util.*;

import org.junit.Test;

import utils.BracketUtils;

public class Ex218 { 
    class Solution1 {
        public List<List<Integer>> getSkyline(int[][] buildings) {
            Map<Integer, Integer> map = new TreeMap<>();
            int len = buildings.length;
            int left, right, height, rightest = 0, leftest = Integer.MAX_VALUE; 
            for (int i = 0; i < len; i++) {
                left = buildings[i][0];
                right = buildings[i][1];
                height = buildings[i][2];

                rightest = Math.max(right, rightest);
                leftest = Math.min(left, leftest);

                for (int j = left; j <= right; j++) {
                    map.put(j, Math.max(height, map.getOrDefault(j, 0)));
                }
            }
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> list;
            int  cur;
            for (int i: map.keySet()) {
                boolean hasLeft = map.containsKey(i - 1),
                hasCur = map.containsKey(i),
                hasRight = map.containsKey(i + 1);
                if (hasCur) {
                    if (!hasLeft) {
                        list = new ArrayList<>();
                        list.add(i);
                        list.add(map.get(i));
                        res.add(list);
                    } else if (!hasRight) {
                        list = new ArrayList<>();
                        list.add(i);
                        list.add(0);
                        res.add(list);
                    } else if ((left = map.get(i - 1)) != (cur = map.get(i))) {
                        list = new ArrayList<>();
                        if (cur > left) {
                            list.add(i);
                        } else {
                            list.add(i - 1);
                        }
                        list.add(cur);
                        res.add(list);
                    }
                }
            }
            return res;
        }
    }

    class Solution {

        /* 
            规律：从轮廓线上看：
            (1)只有从横向轮廓变成纵向轮廓时出现关键点；
            (2)关键点位置的纵向轮廓
                    <一>若是从下往上，则此处纵坐标较大的点为关键点；
                    <二>若从上往下，纵坐标第二者为关键点
                大小的比较是基于 “同一个横坐标的所有候选纵坐标点” 进行的

            难点：
            (1)表名当前纵向的轮廓线的方向是从上往下还是从下往上
                从上往下：将记录的纵坐标点标记为负相反数，这样在遍历处理结果时一看到负数按照规则<一>处理

            (2)纵坐标值的比较：
                使用优先级队列(大顶堆)

            (3)对于“过期”纵坐标的处理 【比如说，从高的横向转为低的纵向时，之前横向的堆顶最大值应当删除，但是只删除一个
            是不够的，比如相邻(2,3,1)的情况，此时关键点高度应当为1，但是按照优先级队列为2，如何删除2？】
            哈希表的延时删除：
            使用哈希表记录应当删除的高度(即出现纵向轮廓由上至下的情况)， 其key为此高度需要删除的次数

            思路：
            使用优先级队列
        */
        public List<List<Integer>> getSkyline(int[][] buildings) {
            List<int[]> points = new ArrayList<>();
            for (int i = 0; i < buildings.length; i++) {
                points.add(new int[]{buildings[i][0], -buildings[i][2]});
                points.add(new int[]{buildings[i][1], buildings[i][2]});
            }

            points.sort((p1, p2) -> {
                if (p1[0] != p2[0]) {
                    return p1[0] - p2[0];
                } else {
                    return p1[1] - p2[1];
                }
            });

            List<List<Integer>> res = new ArrayList<>();
            //大顶堆
            Queue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
            Map<Integer, Integer> map = new HashMap<>(); //删除堆顶元素的次数

            queue.offer(0);
            int last = 0, cur;
            int[] nums;
            for (int i = 0; i < points.size(); i++) {
                nums = points.get(i);
                if (nums[1] < 0) {
                    queue.offer(-nums[1]);
                } else {
                    map.put(nums[1], map.getOrDefault(nums[1], 0) + 1);
                }
                int val, t;
                while (!queue.isEmpty()) {
                    t = queue.peek();
                    if (map.containsKey(t)) {
                        val = map.get(t);
                        map.put(t, val - 1);
                        if (val == 1) {
                            map.remove(t);
                        }
                        queue.poll();
                    } else break;
                }

                cur = queue.peek();
                if (cur != last) {
                    List<Integer> list = Arrays.asList(nums[0], cur);
                    last = cur;
                    res.add(list);
                }
            }
            return res;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[][] nums = BracketUtils.to2DArray("[[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]");
        nums = BracketUtils.to2DArray("[[0,2147483647,2147483647]]");

        System.out.println(s.getSkyline(nums));
    }


    @Test
    public void test2() {
        String s = "(+1)(-1)";
        s = s.replaceAll("[(+,(-]", "(0+");
        System.out.println(s);
    }
}